package com.jacklei.Manachre;


public class Manacher {
    public static void main(String[] args) {
       char[] t = {'1','2','3','4','5','6'};
        int manacher = getManacher("edqweqdasdadq2dwadawewr234242segvfxc");

    }

    public static int getManacher(String s) {
        //将字符串的加工并变为字符数组
        char[] T = getTranCher(s);
        //计算Len数组
        return getLen(T);
    }

    private static int getLen(char[] t) {
        int maxIndex = 0;
        int[] len = new int[t.length];
        len[0] = 1;
        for (int i = 1; i < t.length; i++) {
            //超过最右端的距离R(暴力枚举);
            int maxLen = len[maxIndex];
            if( maxLen <= i - maxIndex){
                int j = 0;
                while (i+j < t.length && i-j >=0 && t[i-j] == t[i+j]){
                    len[i]++;
                    j++;
                }
                maxIndex = len[i] >= len[maxIndex] ? i : maxIndex;
            }else {
                int j = maxIndex - (i - maxIndex);
                //如果 i 的对称 j 回文串完全在 len[maxIndex] 的 内部  -----> len[i] = len[j]
                int lLength= (j - (maxIndex - maxLen));//对称j的回文串的长度R

                if(len[j] < lLength){
                    len[i] = len[j];
                }else if (len[j] > (j - (maxIndex - maxLen))){
                    //如果 i 的对称 j 回文串范围超过 len[maxIndex] 的 内部 -----> len[i] = j - (maxIndex - len[maxIndex])
                    len[i] = j - (maxIndex-maxLen);
                }else {
                    //如果 i 的对称 j 回文串范围恰好在 len[maxIndex] 的 边界 -----> 超出部分继续尝试

                    int k = j - (maxIndex - maxLen);
                    len[i] = lLength;
                    while (i+k < t.length && i-k >=0 && t[i+k] == t[i-k]){
                        len[i]++;
                        k++;
                    }
                    maxIndex = len[i] >= len[maxIndex] ? i : maxIndex;
                }

            }

        }
        return len[maxIndex]/2;
    }

    private static char[] getTranCher(String s) {
        char[] chars = s.toCharArray();
        char[] T = new char[chars.length * 2 + 1];
        for (int i = 0; i < T.length; i++) {
            T[i] = i % 2 == 0 ? '#' :chars[i/2];
        }
        return T;
    }
}
